# assignment2.rb (v1.0)

# Fill this up:
#   Section : G4 (Tue) (please specify correct day)
#   Faculty : Lau Hoong Chuin (please delete one)
#   Team ID : G4-T15
#   Name of Team member 1: Seah Jun Zhi
#   Name of Team member 2: Mohamed Safiullah
#   Name of Team member 3 (if any):

#-------------------------------------------------------------------
# Q3(a)
$visit_Array = Array.new
def get_shortest_link_between_actors (g, x, y)
    q = Queue.new
    # s = Stack.new
    link = Array.new
    routes = Hash.new

    source = g.get_vertex(x)
    target = g.get_vertex(y)

    if source == nil || target == nil
      return nil
    end

    if source== target
      return link << x.to_s
    end

    # flush out visit array
    $visit_Array = Array.new
    #visit source x
    visit(source)
    # put the source as the first in the queue
    q.enqueue(source)

    #placeholder to check which nodes are used to reach from source to target
    chain_intermediate = nil

    #performing a breadth first search algo
    while !q.is_empty?
      #upon entering the vertice, dequeue it
      v= q.dequeue

      if v.adjList.include? target
        chain_intermediate = v
        break
      else
        #checking all the adjacent vertices
        for i in 0..(v.adjList.length-1)
          neighbour = v.adjList[i]

          #if vertice has not been visited
          if !is_visited(neighbour)
            #visit the vertice and place it into the queue
            visit(neighbour)
            q.enqueue(neighbour)
            routes[neighbour] = v
          end
        end
      end
    end

    #place the target as the first in the array
    link << y

    # complete the chain of vertices
    if chain_intermediate != source
        link << chain_intermediate.to_s
      while (chain_intermediate != source)
        previous_vertice = routes[chain_intermediate]
        link << previous_vertice.to_s
        chain_intermediate = previous_vertice
      end
    else
      link << x
    end

    #reverse
    link.reverse!

    return link
end

def visit(vertex)
  $visit_Array << vertex
end

def is_visited(vertex)
  return $visit_Array.include?(vertex)
end

#-------------------------------------------------------------------
# Q3(b)
$routes = Hash.new
$values = Hash.new
def get_closest_link_between_actors (g, x, y)
  # an array of vertices that contains value as the last intermediatory
  # between the source and the key vertice
  $routes = Hash.new
  # an array of vertices that has been visited by the algo containing the
  # distane between the source and the key vertice
  $values = Hash.new

  # flush out visit array
    $visit_Array = Array.new

    # get the chain of characters from target to source
    link = Array.new

    # get the vertice object of source and target
    source = g.get_vertex(x)
    target = g.get_vertex(y)

    # if graph does not contain either the source or target, return nil
    if source == nil || target == nil
      return nil
    end

    # mark the source as visited
    visit(source)
    lowest_value = source.adjListWeights[0].to_f
    lowest_value_vertice = source.adjList[0]

    #loop all the adjacent nodes to check the distances
    for i in 0..(source.adjList.length-1)
      neighbour = source.adjList[i]
      distance = source.adjListWeights[i].to_f

      if lowest_value > distance
        lowest_value = distance
        lowest_value_vertice = neighbour
      end

      $values[neighbour] = distance
      $routes[neighbour] = source
    end

    # if the lowest value vertice is the target, return the chain
    if lowest_value_vertice == target
        link << source.to_s
        link << target.to_s
        return link
    end

    # perform dijkstra algo to reach the target vertice
    target_vertice_reached = dijkstra_traversal(g, lowest_value_vertice, target, lowest_value)

    # temp vertice to find intermediate vertice
    intermediate_vertice = target_vertice_reached

    # loop till source vertice has been found
    if intermediate_vertice != source
      while (intermediate_vertice != source)
        link << intermediate_vertice.to_s
        intermediate_vertice = $routes[intermediate_vertice]
      end
    end

    #adding source vertice to link
    link << source.to_s
    link.reverse!

    #reverse
    return link
end

def dijkstra_traversal(g, x, y, intermediate_distance)
  # visit vertice
  visit(x)

  # loop through all neighbouring vertices surrounding the lowest value vertice, x
  for i in 0..(x.adjList.length - 1)
    neighbour = x.adjList[i]
    distance = x.adjListWeights[i].to_f

    # check if the vertices has been visited, if it is not check the distance between
    # existing vertice and the neighbour
    if !is_visited(neighbour)
      if $values[neighbour] != nil
        if $values[neighbour] > (intermediate_distance + distance)
          $values[neighbour] = intermediate_distance + distance
          $routes[neighbour] = x
        end
      else
        #i.e. has not been visited and is a newly discovered vertice
        $values[neighbour] = intermediate_distance + distance
        $routes[neighbour] = x
      end
    end
  end

  lowest_value = 999999
  lowest_value_vertice = x

  #check the lowest value vertice amongst the unvisited ones
  $values.each { |vertice, distance|
    if lowest_value > distance && !is_visited(vertice)
      lowest_value = distance
      lowest_value_vertice = vertice
    end
  }

  # if lowest value vertice is the target, return target
  if lowest_value_vertice == y
    return y
  else
    # check the intermediate distance
    intermediate_distance = lowest_value

    # loop the traversal till the target has been found
    return dijkstra_traversal(g, lowest_value_vertice, y, intermediate_distance)
  end


end
#-------------------------------------------------------------------



#----------------------------------------------------------------------------------------------------------
#Q4
def greedy(vertices, s)
  #puts "greedy algo"

  return s if vertices.empty?

  max = -1
  v_max_index = -1

  i=0
  vertices.each { |v|
    num_adjoinable_vertices = vertices.size - (vertices & v.adjList).size - 1

    #puts "v = #{v}, rho= #{num_adjoinable_vertices}"

    if num_adjoinable_vertices > max
      max = num_adjoinable_vertices
      v_max_index = i
    end

    i+=1
  }

  #puts "v_max= #{vertices[v_max_index]}, rho= #{max}"
  #puts ""

  v = vertices[v_max_index]
  s << v
  vertices.delete_at(v_max_index)
  v.adjList.each { |w|
    vertices.delete(w)
  }

  #puts "s #{s}"
  #puts "vertices #{vertices}"

  return greedy(vertices, s)

end


def compute_sufficient_size_for_maximum_independent_set(g)
  #a mathematical formula states that the number of independent actors is at least k
  #where k = n/(m+1), rounded up to the nearest integer
  #m is the maximum vertex degree in the graph, (i.e. the max number of neighbours)

  n = g.count_v

  max_degree = 0
  g.vertices.each { |v|

      #get degree of v (i.e. num of neighbours)
      degree = v.adjList.size
      max_degree = degree if degree > max_degree
  }

  #compute sufficient size for maximum independent set
  sufficient_size = ( n / (max_degree+1.0) ).ceil #ceil means ceiling (i.e. round up)

  #puts
  #puts "n=#{n}, max_degree=#{max_degree}, k=#{sufficient_size}"

  return sufficient_size
end

def delete_neighbours(vertices, v)
  v.adjList.each { |w|
    vertices.delete(w)
  }
end


def local_search(vertices, s)

  #s_vw = s.clone
  x = nil
  w = nil

  vertices.each { |v|
    w = v.adjList & s
    if w.size == 1
      x = w[0]
      s.delete(x)
      s << v

      break;
    end
  }

  vertices.delete(x)
  vertices |= w

  s.each { |y|
    delete_neighbours(vertices, y)
    vertices.delete(y)
  }
  return greedy(vertices, s)
end


def run_algo(g)

  #time = Time.now

  k = compute_sufficient_size_for_maximum_independent_set(g)

  #PART 1
  mis = []
  mis_selected = []

  g.vertices.each { |v|
    s = [v]

    #-- calling of greedy algo --
    vertices_copy = g.vertices.clone
    delete_neighbours(vertices_copy, v)
    vertices_copy.delete(v)
    #puts
    #puts "s= #{s}"
    #puts "vertices= #{vertices_copy}"
    s = greedy(vertices_copy, s)
    #if we  have a set size of at least k
    mis << s
    mis_selected << s if s.size >= k
    break if mis.size == 5
    #-- calling of greedy algo end --
  }

  ans = []
  #mis = mis_selected if mis_selected == 3

  #PART 2
  n = mis.size
  for i in 0..n-1
    s_i = mis[i]

    for j in 0..n-1
      s_j = mis[j]
      next if s_i == s_j

      s = s_i & s_j

      #-- calling of procedure 1 --
      vertices1 = g.vertices.clone
      s.each { |v|
        delete_neighbours(vertices1, v)
        vertices1.delete(v)
      }
      s = greedy(vertices1, s)
      #base case
      if s.size >= k
        ans << s
        next
      end
      #-- calling of procedure 1 end --

      #-- calling of procedure 2 --
      k.times {
        vertices2 = g.vertices.clone
        s.each { |w|
          vertices2.delete(w)
        }
        s = local_search(vertices2, s)
      }
      #base case
      if s.size >= k
        #maximal_independent_sets << s
        ans << s
        next
      end
      #-- calling of procedure 2 end --

    end

  end


  b = []
  ans.each { |a|
    b = a if a.size > b.size
  }


  #puts "Execution: #{Time.now - time} s"
  #puts "Quality: #{b.size}"

  return b

end



# Q4 - this method will only be invoked AFTER Q3(a) and Q3(b) have been tested on the submission server
def get_largest_set_of_independent_actors (g)
  return run_algo(g)
end
#-------------------------------------------------------------------